package com.cn.algorithm02.class03;

import java.util.*;

/***
 * @author: hels
 * @description: 数组中一种数出现K次， 其他数出现M次， 找出k次的数
 * M>1, K<M
 * 要求时间复杂度为O(N) 额外空间复杂度O(1)
 * 意味着新建有限个变量
 **/
public class C05_KMOdd {

    static int k,m;
    static int maxValue = 30;
    static int kind;

    static int MofNum;

    public static void main(String[] args) {
        /*int[] arr = {1,1,1,2,2,2,-313,-313,5,5,5};
        int ans = findK(arr,2,3);
        System.out.println("结果是： " + ans);*/

        for (int i = 0; i < 10; i++) {
            int[] arr = creatArr();
            int ans = findK(arr,k,m);
            if (ans != MofNum) {
                System.out.println("有误");
            }
            System.out.println("===========本次ans" + ans);

        }
        System.out.println("测试完成");



       /* Random r = new Random();
        HashSet<Integer> set = new HashSet<>();
        do {
            int num = r.nextInt(maxValue) - r.nextInt(maxValue);
            set.add(num);
        } while (set.size() < 5);
        System.out.println(set);*/


        /*for (int i = 0; i < 32; i++) {
            System.out.println(Integer.toBinaryString(((0x8000_0000)>>i)));
        }*/


      /*  System.out.println("==========");
        // 右移动几位，就是2的几次方
        System.out.println(1<<0);// 2^0
        System.out.println(1<<1);// 2^1
        System.out.println(1<<4);// 2^4*/
    }

    public static int findK(int[] arr, int k, int m) {
        int[] times = new int[32];
        int ans = 0;

        for (int num: arr) {
            for (int i = 0; i < 32; i++) {
                if (((num>>i) & 1) == 1) { // >> 左边用符号位进行补位
                    times[i] += 1;
                }
            }
        }

        // 判断times元素是否除k取余，有余数的
        for (int i = 0; i < 32; i++) {
            if (times[i] % m == k) {
                ans |= (1<<i);
            }
        }

        return ans;
    }

    // 随机生成数组队列，k, m 次
    public static int[] creatArr() {
        Random r = new Random();
        int num1 = r.nextInt(9) + 1;
        int num2 = r.nextInt(9) + 1;
        k = Math.min(num1, num2);
        m = Math.max(num1, num2);
        if (k ==m ){
            m++;
        }
        kind = r.nextInt(10) + 2; // 保证kind数量不小于2
        int size = k + m * (kind - 1);
        int[]  arr = new int[size];

        HashSet<Integer> set = new HashSet<>();  // set 惟一值,且只有kind个
        do {
            int num = r.nextInt(maxValue) - r.nextInt(maxValue);
            set.add(num);
        } while (set.size() < kind);

        // 随机执行m次的数
        ArrayList<Integer> list = new ArrayList<>(set);
        int kindex = r.nextInt(kind);
        MofNum = list.get(kindex);
        for (int i = 1; i < k; i++) {
            list.add(list.get(kindex));
        }

        for (int i = 1; i < m; i++) {
            for (int j = 0; j < kind; j++) {
                if (j != kindex) {
                    list.add(list.get(j));
                }

            }
        }
        System.out.println("set: " + set );
        System.out.println("k: " + k + " m:" + m + " kindex: " + kindex);
        System.out.println(size + " , list.size :" + list.size());
        System.out.println(list);
        for (int i = 0; i < size; i++) {
            arr[i] = list.get(i);
        }

        return arr;
    }
}
